package com.zlk.algorithm.algorithm.dynamicPlan.longestIncreasingSubsequence;

/**
 * @author fsl
 */
// 最长递增子序列和最长不下降子序列
// 给定一个整数数组nums
// 找到其中最长严格递增子序列长度、最长不下降子序列长度
// 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/
public class Code01_LongestIncreasingSubsequence {

    // dp[i] 以i结尾的最长递增子序列长度
    //暴力版动态规划
    public int lengthOfLIS(int[] arr) {
        int n = arr.length;
        //最长递增dp
        // 以i结尾最长递增自序列长度
        //  dp[i]
        int[] dp = new int[n];
        //最长递减dp
        int ans =0;
        dp[0]=1;//第一位就是递增或者递减
        for (int i = 0; i < n; i++) {
            //求i之前最长递增子序列长度
            dp[i]=1;
            for (int j = 0; j <i ; j++) {
                if(arr[i]>arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
                ans = Math.max(dp[i],ans);
            }
        }
        return ans;
    }

    //最长递减子序列
    public int lengthOfLISDecrse(int[] arr) {
        int n = arr.length;
        int[] dp =new int[n];
        dp[n-1] = 1;
        int ans = 1;
        for (int i = n-1; i >=0 ; i--) {
            dp[i] =1;
            for (int j = n-1; j >i ; j--) {
                if(arr[i]>arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
                ans = Math.max(ans,dp[i]);
            }
        }
        return ans;
    }

    //最优解动态规划 todo
    //ends数组+二分查找
    // 时间复杂度 n*logN
    // dp[i]含义以i位置结尾的最长递增子序列长度
    // ends[i]目前所有长度 i+1的递增子序列的最小结尾
    // 通过查找大于nums[i]的最左位置，定位跟新ends[i]，
    // 计算ends 中i位置前面有几个数定位dp[i]的值，为啥可以，因为ends数组是递增有序的，为啥有序见 index.md
    // 那为啥统计ends前面有几个数就是dp[i]的值，因为ends的含义
    //数组  10, 9, 2, 5, 3, 7, 101, 18
    //ends 10
    //dp   1
    //
    //ends 9
    //dp   1   1
    //
    //ends 2
    //dp   1   1  1
    //
    //ends 2   5
    //dp   1   1  1 2
    //
    //ends 2   3
    //dp   1   1  1 2 2
    //
    //ends 2   3  7
    //dp   1   1  1 2 2  3
    //
    //ends 2   3  7 101
    //dp   1   1  1 2 2  3  4
    // final
    //ends 2   3  7 18
    //dp   1   1  1  2  2 3 4 4
    public int lengthOfLIS2(int[] nums) {
        int n = nums.length;
        //目前n长度的最长子序列的最小结尾数
        int[] ends = new int[n];
        ends[0] = nums[0];
        int activeLen = 1;//ends数组扩充的有效长度
        for (int i = 1; i <n; i++) {
            int index = findLeftIndex(ends,activeLen,nums[i]);
            if(index == -1){
                ends[activeLen++] = nums[i];
            }else{
                ends[index] =nums[i];
            }
        }
        return activeLen;
    }

    //二分法求解
    private int findLeftIndex(int[] ends, int activeLen, int num) {
        int left = 0;
        int right = activeLen-1;
        int mid = 0;
        int ans = -1;
        while (left<=right){
            mid = (right+left)/2;
            if(ends[mid]>=num){//为啥要大于而等于，应为等于的时候不算递增，所以要替换
                ans = mid;
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return ans;
    }

    // 如果求最长不下降子序列，那么使用如下的二分搜索 :
    // ends[0...len-1]是不降序的
    // 在其中找到>num的最左位置，如果不存在返回-1
    // 如果求最长不下降子序列，就在lengthOfLIS中把bs1方法换成bs2方法
    // 已经用对数器验证了，是正确的
    public static int bs2(int[] ends, int len, int num) {
        int l = 0, r = len - 1, m, ans = -1;
        while (l <= r) {
            m = (l + r) / 2;
            if (ends[m] > num) {//等于的时候也要计算长度
                ans = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return ans;
    }


}
